1. Technical Field
The present invention relates to apparatus for forwarding packets in a data network, and to associated methods of forwarding packets, and to related manners and apparatus for performing such methods.
2. Related Art
Many different quality-of-service (QoS) mechanisms have been proposed for packet-switched communications networks such as the Internet. The use of Resource Reservation Protocol (RSVP) with IntServ enables explicit reservation of capacity for traffic that requires guaranteed bandwidth with low packet drop probability. By contrast, Differentiated Services (DiffServ) enables relative prioritisation of different ‘best-effort’ traffic classes, which do not require explicit bandwidth or packet drop guarantees. More recently the development of traffic-engineered multi-protocol label switching (MPLS-TE) has enabled efficient bandwidth management.
Another control mechanism that is relevant to the invention is the use of token buckets and leaky buckets in order to regulate packet flows [1]. In the past these algorithms have been used to smooth packet flows and to police them to ensure specified peak rates.
An alternative approach to providing bandwidth guarantees is the use of measurement-based admission control [2,3,4,5,6,7]. With this type of scheme, routers make measurements of load or congestion across a region of the network. These measurements are used as the basis for admission control decisions by which new demands for guaranteed quality connections are accepted or rejected. The advantage of this approach is that routers within the core region do not need to be aware of individual connections (they have no ‘flow-state’), but they might simply apply some form of priority queueing to ensure that packets in guaranteed flows have low delay.
A more radical approach is the use of congestion pricing, for example according to the theory developed by Kelly [8], and studied further in the EU project M3I as a market-based solution to network resource allocation [9]. According to this approach, if end-users are charged in proportion to congestion in the network then they will moderate their demands for bandwidth in accordance with their willingness-to-pay, resulting in a socially optimum allocation of bandwidth. This mechanism also allows end-systems to differentiate between best-effort flows (which will back-off in response to pricing) and flows requiring guaranteed bandwidth (which can accept the pricing and continue sending). A mechanism for signaling congestion already exists—the use of Explicit Congestion Notification (ECN) by which individual packets can be ‘marked’ by a router which is experiencing (or approaching) congestion [10]. ECN was proposed as an enhancement of TCP (Transmission Control Protocol) rate control, allowing end-systems to adapt their rate in response to congestion marks without the need for packet-drops. The use of ECN marks as a basis for congestion charging is a natural development, as set out below.
Explicit Congestion Notification (ECN) has been proposed for use within Internet Protocol (IP) networks, and involves ECN capable routers marking packets as having experienced congestion by the use of specific ECN fields within the packet header, rather than dropping the packet and leaving a receiver of data to infer congestion, as had previously been the case (as packet loss could also be caused by transmission errors, loss of a packet is not a definitive indicator of network congestion). Within IP, a two-bit field within the IP header has been proposed to enable the marking of packets, comprising a first ‘ECN-Capable Transport’ (ECT) bit (which was generally intended to be used to indicate whether the end-points of the transport protocol were ECN capable) and a second ‘Congestion Experienced’ (CE) bit (which was generally intended to be marked by routers in the event of congestion to indicate that the packet has experienced congestion). The use of two bits within the IP header provides four code-points, however, ([ECT,CE]: [0,0], [0,1], [1,0], and [1,1]) and RFC 3168 (reference [10] —see FIG. 1 thereof) defines two of these as being indicative of ECN capability ([0,1] and [1,0], referred to as ECT(1) and ECT(0) respectively), leaving the code-point [0,0] to indicate a lack of ECN capability, and the code-point [1,1] to indicate a ‘Congestion Experienced’ state. Senders of data are free to use either the ECT(0) or the ECT(1) code-point to indicate ECT, on a packet-by-packet basis. The use of both the two code-points for ECT, ECT(0) and ECT(1), is motivated primarily by the desire to allow mechanisms for the data sender to verify that network elements are not erasing the CE codepoint, and that data receivers are properly reporting to the sender the receipt of packets with the CE codepoint set, as required by the transport protocol.
Regarding uses of the ECN marks, it has been proposed that they can be used for both congestion signaling purposes and for congestion pricing. In particular, Henderson et al [14] suggest that since the mark indicates network congestion, the network can aggregate marks to represent a “shadow price” for a flow, reflecting the cost of the congestion which it causes. A problem of using ECN marks to generate the shadow price is that it is not until the packets of a flow have arrived at the receiver that the number of packets in the flow with the CE code-point set can be properly measured, since at any point on the route before this further packets may have the CE code-point set at any router later in the route. There is therefore a problem of generating the level of shadow charges for use on an inter-domain basis between network domains without having knowledge of the total shadow charge which will ultimately arise.
A further development of ECN is the use of a virtual queue for early marking [6,9,11]. A virtual queue simply operates as a counter (not a real packet queue). The counter is incremented by the sizes of arriving packets and decremented at a constant rate that is normally slightly lower than the configured rate of the outgoing route. The size of the virtual queue, at the moment that a packet arrives for sending on the outgoing route, is used to determine an appropriate congestion signal such as an ECN mark. ECN marking may be done probabilistically according to the virtual queue size, using for example an algorithm such as Random Early Detection (RED, [12]). Through the use of a virtual queue, emptied at a rate slightly lower than the configured rate, congestion signaling will start when the actual outgoing buffer is still close to empty, thereby ensuring low packet queueing delay and low risk of packet drop. FIG. 1 illustrates the use of a virtual queue for early congestion marking, with priority queueing being used on the output buffer.
One development arising from the M3I project was a form of measurement-based admission control using ECN, which was known as the Guaranteed Service Provider (GSP). In subsequent developments this is known as Guaranteed QoS Synthesis (GQS). With this approach, illustrated in FIG. 2, a region of the network is surrounded by gateway routers which perform admission control for guaranteed service requests on the basis of the measured rate of ECN marking across the inter-gateway path concerned. Routers within the region may use priority queueing, possibly with pre-emption, in order to give precedence to packets in guaranteed flows. In one form of this scheme best-effort packets are also subject to ECN marking, but best-effort flows are assumed to be rate-adaptive in response to ECN marking whereas guaranteed flows do not adapt their rates. (Note: In practice some best-effort flows may not be ECN-capable but will adapt their rates in response to packet drops, and other best-effort flows may not adapt their rates at all). This scheme retains a key element of a market-based solution—there is strong demand for guaranteed service then best-effort traffic is forced to back off (through rate-adaptation to ECN marking) but if there are many best-effort flows then guaranteed service demands may be rejected (admission control). With the use of appropriate pricing and appropriate marking rate thresholds for admission control, this scheme provides a fair market-based solution. However it is likely that network operators might wish to place constraints on market-based resource sharing, for example by ensuring that each traffic class has access to a guaranteed minimum amount of bandwidth regardless of the demand from the other class, and this scheme has not heretofore provided an efficient mechanism for doing this.
The M3I project [9] have put forward a GSP mechanism that was described in more detail by TUD [13]. Earlier work had proposed admission control based on congestion measurements [6], and also proposed the use of virtual queues [6,11].
Several researchers have also investigated schemes for admission control based on load measurements [2,4,5], and there has also been a proposal to base admission control on measurements of delay variation [7].
Referring to prior art patent documents, European application EP 1,317,151 relates to a method for congestion control signaling for use in a wireless network, and includes a brief review of the uses of ECN marks for congestion control signaling.
U.S. Pat. No. 5,751,969 relates to apparatus and methods for predicting and managing congestion in networks.
U.S. Pat. No. 6,657,962 relates to a system for minimising congestion in a communication system.
UK patent application GB 2,281,005 relates to a manner of self-regulating traffic to avoid congestion in an Asynchronous Transfer Mode (ATM) network.
U.S. patent application US 2003/0097461 relates to systems and methods for controlling network demand via congestion pricing, and includes a discussion of ECN-based schemes.
International patent application WO 03/010909 relates to a system and method for traffic congestion control at the media access controller (MAC) level. The media access controller receives an inbound packet and pre-classifies the packet for determining its priority. A utilisation level of a queue associated with the determined priority is analysed for determining its level of congestion. The packet is admitted or not based on the congestion information. Admitted packets are forwarded to the packet switching controller which engages in further classification and congestion control for determining whether the admitted packet is to be forwarded to a destination address. It will be noted that the response of the above system to congestion is to selectively drop packets such that higher priority packets are forwarded at the expense of lower priority packets.